//
// Created by xili on 2024/9/24 17:06.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution {
public:
    int maximumCostSubstring(string s, string chars, vector<int> &vals) {
        unordered_map<char, int> ump;
        int m = chars.size();
        for (int i = 0; i < m; i++) {
            ump[chars[i]] = i;
        }
        int n = s.size();
        vector<int> dp(n);
        int ans = ump.count(s[0]) ? vals[ump[s[0]]] : s[0] - 'a' + 1;
        dp[0] = ans;
        for (int i = 1; i < n; i++) {
            dp[i] = max(dp[i - 1], 0) + (ump.count(s[i]) ? vals[ump[s[i]]] : s[i] - 'a' + 1);
            ans = max(ans, dp[i]);
        }
        return max(ans, 0);
    }
};